﻿/*Thông tin*********************************************************************
 *Tên tập tin	: Graph_Independent_Set.h
 *Mô tả			: Thư viên các thuật toán tìm tập độc lập
 *Ngày tạo		: 24/10/2012
 *Cập nhật cuối	: 07/11/2012
 *Trình dịch	: Microsoft Visual C++ 11.0
 *Tác giả		: Vũ Văn Hiệp
 *Thư điện tử	: muteszhacker@gmail.com
*******************************************************************************/

/*Lớp các thuật toán tìm tập độc lập*/
class INDEP : public GRAPH	{
private:
	// Kích thước rừng đang duyệt
	uint16_t size;

	// Trọng số cực đại của tập độc lập của cây con T_u chứa u
	vector <double> max_in;
	// Trọng số cực đại của tập độc lập của cây con T_u không chứa u
	vector <double> max_out;
	// Mảng lưu giá trị max(max_in[i], max_out[i])
	vector <double> big;
	// Trọng số ứng với mỗi đỉnh v - là trọng số cạnh (v, i) lớn nhất
	vector <double> weight;

public:
	// Phương thức khởi tạo
	INDEP();

	// Khởi tạo thuật toán tìm tập độc lập kích thước lớn nhất
	void Initiate_indep_set();

	// Bổ sung cạnh theo chiều ngược lại cho mỗi cạnh đã có
	void Add_reverse_edges();
	// Tìm cạnh (u, v) có v là lá
	EDGE INDEP :: Find_edge_of_leaf();
	// Thuật toán tìm tập độc lập kích thước lớn nhất với đồ thị cây/rừng
	void Find_max_size_indep_set();
	// In kết quả tìm kiếm tập độc lập kích thước lớn nhất ra file .out
	void Print_max_size_indep_set_to_out(string input_file);
	// In tập độc lập kích thước lớn nhất ra file .dot
	void Print_max_size_indep_set_to_dot(string input_file);

	// Tính big(v) tại v
	void Calculate_big(uint16_t v);
	// Thuật toán tìm tập độc lập có trọng số lớn nhất với đồ thị cây/rừng
	void Max_tree(uint16_t v);
	// In thông báo kết thúc thuật toán tìm tập độc lập có trọng số lớn nhất
	void Find_max_weight_indep_set();
	// Xây dựng mảng kết quả result
	void Build_result();
	// In kết quả tìm kiếm tập độc lập có trọng số lớn nhất ra file .out
	void Print_max_weight_indep_set_to_out(string input_file);
	// In tập độc lập có trọng số lớn nhất ra file .dot
	void Print_max_weight_indep_set_to_dot(string input_file);
};/*Kết thúc khai báo lớp INDEP*/

/*Phương thức khởi tạo*/
INDEP :: INDEP()	{
	size = 0;
	max_in.clear();
	max_out.clear();
	big.clear();
	weight.clear();
}/*Kết thúc phương thức INDEP*/

/*Khởi tạo các thông tin cơ bản của đồ thị*/
void INDEP :: Initiate_indep_set()	{
	result.clear();
	
	cout << "Thuc hien thuat toan tim kiem tap doc lap..........";
	start_time = clock();
}/*Kết thúc hàm Initiate_indep_set*/

// Bổ sung cạnh theo chiều ngược lại cho mỗi cạnh đã có
void INDEP :: Add_reverse_edges()	{
	for (uint16_t i=0; i!=Get_vertices(); ++i)
		for (uint16_t j=0; j!=Get_vertices(); ++j)
			if (Get_length(i, j) != Get_length(j, i) && Get_length(i, j)!=UINT16_MAX)	{
				Set_length(j, i, Get_length(i, j));
				Set_edges(Get_edges() + 1);
			}
}/*Kết thúc phương thức Add_reverse_edges*/

/*Tìm cạnh e = (u, v) có v là lá*/
GRAPH :: EDGE INDEP :: Find_edge_of_leaf()	{
	EDGE e;
	e.source = e.target = UINT16_MAX;

	for (uint16_t i=0; i!=neighbors.size(); ++i)	{
		for (uint16_t j=0; j!=neighbors[i].size(); ++j)	{
			e.target = neighbors[i][j];

			if (neighbors[e.target].size() == 1)	{
				e.source = i;

				result.push_back(e.target);
				final[e.target] = true;

				return e;
			}
		}
	}

	return e;
}/*Kết thúc phương thức Find_edge_of_leaf*/

/*Thuật toán tìm tập độc lập kích thước lớn nhất với đồ thị cây/rừng*/
void INDEP :: Find_max_size_indep_set()	{
	Add_reverse_edges();

	size = Get_edges();
	Build_neighbors();

	final.resize(Get_vertices());

	while (size)	{
		EDGE e = Find_edge_of_leaf();

		// Nếu tìm được cạnh
		if (e.source != UINT16_MAX)	{
			// Kiểm tra v có phải là lá duy nhất
			bool only_leaf = true;
			uint16_t u = e.source, v = e.target;

			for (uint16_t i=0; i!=neighbors[u].size(); ++i)	{
				uint16_t leaf = neighbors[u][i];

				if (leaf!=v && neighbors[leaf].size()==1)	{
					only_leaf = false;
					break;
				}
			}

			// Nếu là lá duy nhất thì xóa hết tất cả các con của u
			if (only_leaf)	{
				size -= neighbors[u].size();
				neighbors[u].clear();
				final[u] = true;

				// Xóa các cạnh nối đến u
				for (uint16_t k=0; k<neighbors.size(); ++k)
					for (uint16_t t=0; t<neighbors[k].size(); ++t)
						if (neighbors[k][t] == u)	{
							neighbors[k].erase(neighbors[k].begin()+t);

							--size;
						}

			}
			// Còn không là lá duy nhất thì chỉ xóa nó thôi
			else	{
				neighbors[v].clear();
				--size;

				for (uint16_t i=0; i!=neighbors[u].size(); ++i)
					if (neighbors[u][i] == v)	{
						neighbors[u].erase(neighbors[u].begin() + i);
						--size;
						break;
					}
			}
		}
		else
			break;
	}

	// Nếu còn đỉnh nào chưa xét mà nằm trơ không có cạnh nào liên quan thì thêm nó vào result
	for (uint16_t i=0; i!=neighbors.size(); ++i)
		if (neighbors[i].size() == 0 && !final[i])	{
			result.push_back(i);
			final[i] = true;
		}

	Print_runtime();
}/*Kết thúc hàm Find_max_size_indep_set*/

/*In kết quả tìm kiếm tập độc lập kích thước lớn nhất ra file .out*/
void INDEP :: Print_max_size_indep_set_to_out(string input_file)	{
	string input_header(input_file.begin(), input_file.end()-4);
	fstream f = New_output_file(input_header, "_Indep", ".out");

	// Bắt đầu in kết quả ra file
	if (size)
			f << "Do thi da cho khong phai la rung.\n";
	else	{
		f << "Cac dinh trong tap doc lap lon nhat la: \n";

		for (uint16_t i=0; i!=result.size(); ++i)
			f << result[i] + 1 << " ";

		f << "\n";
	}

	f.close();
	cout << "Xong.\n";
}/*Kết thúc hàm Print_max_size_indep_set_to_out*/

/*In tập độc lập kích thước cực đại ra file .dot*/
void INDEP :: Print_max_size_indep_set_to_dot(string input_file)	{
	string input_header(input_file.begin(), input_file.end()-4);
	fstream f = New_output_file(input_header, "_Indep", ".dot");

	// Bắt đầu in file
	f << "graph " << input_header << "_Indep" << " {\n";

	if (size)	{
		f << "label = \"\\n\\nDo thi nhap tu file " << input_file 
		  << " khong phai la rung.\"\n}";
	}
	else	{
		// Các đỉnh nằm trong tập kết quả được tô màu đỏ
		f << "node [style = filled, color = red]";
		for (uint16_t i=0; i!=result.size(); ++i)
			f << " " << result[i]+1;
		f << "\n";

		// Các đỉnh còn lại tô màu xanh
		f << "node [style = filled, color = green]";
		vector <uint16_t> b(Get_vertices());

		for (uint16_t i=0; i!=Get_vertices(); ++i)
			b[i] = i+1;

		for (uint16_t i=0; i!=result.size(); ++i)
			b[result[i]] = UINT16_MAX;

		for (uint16_t i=0; i!=Get_vertices(); ++i)
			if (b[i] != UINT16_MAX)
				f << " " << b[i];
		f << "\n";

		for (uint16_t i=0; i<Get_vertices(); ++i)
			for (uint16_t j=0; j<Get_vertices(); ++j)
				if (Get_length(i, j) != UINT16_MAX)	{
					if (i<j)
						f << i+1 << " -- " << j+1 << " [label = \"" << Get_length(i, j) << "\"]\n";
					else	{
						f << i+1 << " -- " << j+1 << " [color = white]\n";
					}
				}

		f << "label = \"\\n\\nTap doc lap lon nhat cua rung\\nvoi du lieu tu file " << input_file << "\"\n}";
	}
	
	f.close();
	cout << "Xong.\n";
}/*Kết thúc hàm Print_max_size_indep_set_to_dot*/

/*Tính big[v]*/
void INDEP :: Calculate_big(uint16_t v)	{
	max_in[v] = weight[v];
	max_out[v] = 0.0;

	for (uint16_t u=0; u!=neighbors[v].size(); ++u)	{
		max_in[v] += max_out[neighbors[v][u]];
		max_out[v] += big[neighbors[v][u]];
	}

	big[v] = max_in[v] > max_out[v] ? max_in[v] : max_out[v];
}/*Kết thúc hàm Calculate_big*/

/*Thuật toán tìm tập độc lập có trọng số lớn nhất với đồ thị cây/rừng*/
void INDEP :: Max_tree(uint16_t v)	{
	for (uint16_t u=0; u!=neighbors[v].size(); ++u)
		Max_tree(neighbors[v][u]);
	
	Calculate_big(v);
}/*Kết thúc hàm Find_max_weight_indep_set*/

/*In thông báo kết thúc thuật toán tìm tập độc lập có trọng số lớn nhất*/
void INDEP :: Find_max_weight_indep_set()	{
	// Khởi tạo mảng weight
	weight.resize(Get_vertices());
	srand(uint16_t(time(0)));
	
	for (uint16_t i=0; i!=Get_vertices(); ++i)
		weight[i] = uint16_t( rand() ) % 10 + 1;
	
	max_in.resize(Get_vertices());
	max_out.resize(Get_vertices());
	big.resize(Get_vertices());
	Build_neighbors();

	Max_tree(0);
	
	Print_runtime();
}/*Kết thúc hàm Find_max_weight_indep_set*/

/*Xây dựng mảng kết quả result*/
void INDEP :: Build_result()	{
	if (max_in[0] > max_out[0])
		result.push_back(0);

	for (uint16_t j=1; j!=Get_vertices(); ++j)	{
		// Tìm cha của j là i
		uint16_t i;
		bool found = false;

		for (i=0; i!=Get_vertices(); ++i)	{
			for (uint16_t k=0; k!=neighbors[i].size(); ++k)
				if (neighbors[i][k] == j)	{
					found = true;
					break;
				}

			if (found)
				break;
		}

		if (found)	{
			// Kiểm tra xem i có nằm trong result không
			bool in_result = false;

			for (uint16_t k=0; k!=result.size(); ++k)
				if (result[k] == i)	{
					in_result = true;
					break;
				}

			// Thêm j vào result nếu i chưa nằm trong result và max_in[j] > max_out[j]
			if (!in_result && max_in[j] > max_out[j])
				result.push_back(j);
		}
	}
}/*Kết thúc hàm Build_result*/

/*In kết quả tìm kiếm tập độc lập có trọng số lớn nhất*/
void INDEP :: Print_max_weight_indep_set_to_out(string input_file)	{
	string input_header(input_file.begin(), input_file.end()-4);
	fstream f = New_output_file(input_header, "_Max_indep", ".out");

	// Bắt đầu in kết quả
	if (big[0] == 0.0)
			f << "Do thi da cho khong phai la cay.\n";
	else	{
		f << "Cac dinh trong tap doc lap trong so cuc dai " << big[0] << " la: \n";

		for (uint16_t i=0; i!=result.size(); ++i)
			f << result[i] + 1 << " ";

		f << "\n";
	}

	f.close();
	cout << "Xong.\n";
}/*Kết thúc hàm Print_max_weight_indep_set_to_out*/

/*In tập độc lập có trọng số lớn nhất ra file .dot*/
void INDEP :: Print_max_weight_indep_set_to_dot(string input_file)	{
	string input_header(input_file.begin(), input_file.end()-4);
	fstream f = New_output_file(input_header, "_Max_indep", ".dot");

	// Bắt đầu in file
	f << "graph " << input_header << "_Max_indep" << " {\n";

	if (big[0] == 0.0)	{
		f << "label = \"\\n\\nDo thi nhap tu file " << input_file 
		  << " khong phai la cay.\"\n}";
	}
	else	{
		// Các đỉnh nằm trong tập kết quả được tô màu đỏ
		f << "node [style = filled, color = red]";
		for (uint16_t i=0; i!=result.size(); ++i)
			f << " " << result[i]+1 << "." << weight[result[i]];
		f << "\n";

		// Các đỉnh còn lại tô màu xanh
		f << "node [style = filled, color = green]";
		vector <uint16_t> b(Get_vertices());

		for (uint16_t i=0; i!=Get_vertices(); ++i)
			b[i] = i;

		for (uint16_t i=0; i!=result.size(); ++i)
			b[result[i]] = UINT16_MAX;

		for (uint16_t i=0; i!=b.size(); ++i)
			if (b[i] != UINT16_MAX)
				f << " " << b[i]+1 << "." << weight[b[i]];
		f << "\n";
		
		for (uint16_t i=0; i<Get_vertices(); ++i)
			for (uint16_t j=0; j<Get_vertices(); ++j)	{
				if (Get_length(i, j) != UINT16_MAX)
					f << i+1 << "." << weight[i] << " -- " << j+1 << "." << weight[j] 
					  << " [label = \"" << Get_length(i, j) << "\"]\n";
			}

		f << "label = \"\\n\\nTap doc lap trong so cuc dai " << big[0] 
		  << "\\ncua cay voi du lieu tu file " << input_file << "\"\n}";
	}
	
	f.close();
	cout << "Xong.\n";
}/*Kết thúc hàm Print_max_weight_indep_set_to_dot*/
